package org.leetcode.middle.leetcode5;

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        //dp数组是一个正方形的1/2
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;

        int maxLength = 1;
        String res = s.substring(0, 1);

        for (int right = 1; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left) == s.charAt(right)) {
                    if (dp[left + 1][right - 1] || right - left <= 2) {
                        dp[left][right] = true;
                        if (right - left + 1 > maxLength) {
                            maxLength=right-left+1;
                            res = s.substring(left, right + 1);
                        }
                    }
                }
            }
        }

        return res;
    }
}
